#pragma once
#include <iostream>
#include <vector>
#include <map>
namespace MyDSU
{
	class DSU
	{
	public:
		DSU(const size_t& n)
			:_dsu(n, -1)
		{}
		bool MergeSet(const size_t& x1, const size_t& x2)
		{
			size_t root_x1 = findroot(x1), root_x2 = findroot(x2);
			if (root_x1 == root_x2) return false;
			if (_dsu[root_x1] > _dsu[root_x2]) std::swap(root_x1, root_x2);
			_dsu[root_x1] += _dsu[root_x2];
			_dsu[root_x2] = root_x1;
			return true;
		}
		size_t findroot(const size_t& x)
		{
			size_t parent = x;
			while (_dsu[parent] >= 0) parent = _dsu[parent];
			return parent;
		}
		bool SameSet(const size_t& x1, const size_t& x2) { return findroot(x1) == findroot(x2); }
	private:
		std::vector<int> _dsu;
	};
}